public class MergeSort {
	public static int[] mergeSort(int[] data,int high,int low){
		int mid=(low+high)/2;
		//递归拆分 if ,while在这里的作用
		if(low<high){
			// if(low==mid) System.out.println("low==mid");
			mergeSort(data,mid,low);
			mergeSort(data,high,mid+1);
			//合并
			merge(data,high,low,mid);
		}		
		return data;
	}
	public static int[] merge(int[] data,int high,int low,int mid){
		int[] tempdata=new int[high-low+1];
		int index1=low;
		int index2=mid+1;
		int index=0;
		while(index1<=mid&&index2<=high){
			if(data[index1]>data[index2]){
			    tempdata[index++]=data[index2++];
			}else {
				tempdata[index++]=data[index1++];				
			}
		}
		while(index2<=high) 
                tempdata[index++]=data[index2++];		
		while(index1<=mid)
				tempdata[index++]=data[index1++];
		for(int i=0;i<tempdata.length;i++){
			data[i+low]=tempdata[i];
		}
		return data;
	}
	public static void main(String[] args) {
		int[] a={4,3,6,2,7,5,9,1,10,23,-7,11,45,11,23,0,-2,-1,100,15};
		int[] b=mergeSort(a,19,0);
		for(int temp:b)
			System.out.print(temp+"  ");
	}

}
